package dynamicProgramming

import "math"

// 动态规划状态转移方程法--迷宫最短路径
// 备忘录
// 调用方式 MinDistDpEquation(n-1,n-1) 从终点到起点
func MinDistDpEquation(i, j, n int, matrix, mem [][]int) int {
	// 到达起始位置
	if i == 0 && j == 0 {
		return matrix[0][0]
	}
	// 用mem记录已经走过的节点
	if mem[i][j] > 0 {
		return mem[i][j]
	}
	// 往左走
	minLeft := math.MaxInt64
	if j-1 >= 0 {
		minLeft = MinDistDpEquation(i, j-1, n, matrix, mem)
	}

	// 往上走
	minUp := math.MaxInt64
	if i-1 >= 0 {
		minUp = MinDistDpEquation(i-1, j, n, matrix, mem)
	}

	currMinDist := matrix[i][j] + Min(minLeft, minUp)
	mem[i][j] = currMinDist

	return currMinDist
}
